package org.liaohailong.helloworld.example;

/**
 * Author: liaohailong
 * Time: 2021/5/12 09:27
 * Describe:
 */
public class BST<K extends Comparable<K>, V> {
    private Node<K, V> root;

    public void add(K key, V value) {
        if (root == null) {
            root = new Node<>(key, value);
        } else {
            Node<K, V> t = root;
            Node<K, V> parent = null;
            int cmp = -1;
            while (t != null) {
                parent = t;
                cmp = key.compareTo(t.key);
                if (cmp < 0) {
                    t = t.left;
                } else if (cmp > 0) {
                    t = t.right;
                } else {
                    t.value = value;
                    return;
                }
            }
            if (cmp < 0) {
                parent.left = new Node<>(key, value);
            } else {
                parent.right = new Node<>(key, value);
            }
        }
    }

    public Node<K, V> getRoot() {
        return root;
    }

    public static final class Node<K extends Comparable<K>, V> {
        K key;
        V value;
        Node<K, V> left;
        Node<K, V> right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
